|
In computability theory, traditionally called recursion theory, a set ''S'' of natural numbers is called recursively enumerable, computably enumerable, semidecidable, provable or Turing-recognizable if: *There is an algorithm such that the set of input numbers for which the algorithm halts is exactly ''S''. Or, equivalently, *There is an algorithm that enumerates the members of ''S''. That means that its output is simply a list of the members of ''S'': ''s''1, ''s''2, ''s''3, ... . If necessary, this algorithm may run forever. The first condition suggests why the term ''semidecidable'' is sometimes used; the second suggests why ''computably enumerable'' is used. The abbreviations r.e. and c.e. are often used, even in print, instead of the full phrase. In computational complexity theory, the complexity class containing all recursively enumerable sets is RE. In recursion theory, the lattice of r.e. sets under inclusion is denoted . == Formal definition == A set ''S'' of natural numbers is called recursively enumerable if there is a partial recursive function whose domain is exactly ''S'', meaning that the function is defined if and only if its input is a member of ''S''. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「recursively enumerable set」の詳細全文を読む スポンサード リンク
|